package com.dmall.graph.euler;

import com.dmall.graph.Graph;
import com.dmall.graph.dfs.app.CC;

import java.util.*;

/**
 * 使用 hierholzer 算法寻找欧拉回路
 * @author: xiao1.wang
 * @date: 2022/7/31 15:52
 */
public class EulerLoopHierholzer {

    private Graph G;

    public EulerLoopHierholzer(Graph G) {
        this.G = G;
    }

    public boolean hasEulerLoop() {
        CC cc = new CC(G);
        if (cc.count() > 1) {
            return false;
        }
        for (int v = 0; v < G.V(); v++) {
            if (G.degree(v) % 2 == 1) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> result() {
        List<Integer> res = new ArrayList<>();
        if (!hasEulerLoop()) {
            return res;
        }
        Graph g = (Graph) G.clone();
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        while (!stack.isEmpty()) {
            int v = stack.peek();
            if (g.degree(v) == 0) {
                res.add(v);
                stack.pop();
            } else {
                int w = g.adj(v).iterator().next();
                g.removeEdge(v, w);
                stack.push(w);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String filename = EulerLoopHierholzer.class.getClassLoader().getResource("g.txt").getPath();
        Graph g = new Graph(filename);
        EulerLoopHierholzer el = new EulerLoopHierholzer(g);
        System.out.println(el.result());

        String filename2 = EulerLoopHierholzer.class.getClassLoader().getResource("g2.txt").getPath();
        Graph g2 = new Graph(filename2);
        EulerLoopHierholzer el2 = new EulerLoopHierholzer(g2);
        System.out.println(el2.result());
    }
}
